package Demo02;

import java.util.HashMap;

public class LRUCache {
    static class DLinkNode {
        int key;
        int value;
        DLinkNode prev;
        DLinkNode next;

        public DLinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public DLinkNode() {
        }
    }

    public DLinkNode head;//头结点
    public DLinkNode tail;//尾节点

    public int capacity;//容量
    public int usedSize;

    HashMap<Integer, DLinkNode> map = new HashMap<>();

    public LRUCache(int capacity) {
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
    }

    public void put(int key, int value) {
        DLinkNode node = map.get(key);
        //不存在该元素
        if (node == null) {
            //创建新的节点
            DLinkNode newNode = new DLinkNode(key, value);
            map.put(key, newNode);
            //尾插
            insertTail(newNode);
            usedSize++;
            //检查是否元素填满
            if (usedSize > capacity) {
                //头删
                int headKey = deleteHead().key;
                map.remove(headKey);
                usedSize--;
            }
        } else {
            //存在该元素
            node.value = value;
            //删除该元素
            deleteNode(node);
            //尾插元素
            insertTail(node);
        }
    }

    private DLinkNode deleteHead() {
        DLinkNode del = head.next;
        head.next = del.next;
        del.next.prev = head;
        return del;
/*        int key = head.next.key;
        head.next = head.next.next;
        head.next.next.prev = head;
        return key;*/
    }

    public int get(int key) {
        DLinkNode node = map.get(key);
        if (node == null) {
            //不存在
            return -1;
        }
        deleteNode(node);
        insertTail(node);
        return node.value;
    }

    private void deleteNode(DLinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }


    private void insertTail(DLinkNode newNode) {
        DLinkNode tmpNode = tail.prev;
        tail.prev = newNode;
        newNode.next = tail;
        newNode.prev = tmpNode;
        tmpNode.next = newNode;
    }

    private void print() {
        DLinkNode cur = head.next;
        while (cur != tail) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(100, 10);
        lruCache.put(110, 11);
        lruCache.put(120, 12);
        System.out.println("获取元素");
        lruCache.print();
        System.out.println(lruCache.get(110));
        lruCache.print();
        System.out.println(lruCache.get(100));
        lruCache.print();
        System.out.println("存放元素,会删除头节点，因为头节点是最近最少使用的: ");
        lruCache.print();
        lruCache.put(999, 99);
        lruCache.print();
    }
}
